package unionFind;

import java.util.ArrayList;
import java.util.List;

/**
 * 130. 被围绕的区域
 */
public class P130 {
    public void solve(char[][] board) {
        boolean[][] visit = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (!visit[i][j] && board[i][j] == 'O') {
                    List<int[]> savedList = new ArrayList<>();
                    List<Boolean> flagMap = new ArrayList<>();
                    dfs(board, visit, i, j, savedList, flagMap);
                    if (flagMap.size() == 0) {
                        for (int[] point : savedList) {
                            board[point[0]][point[1]] = 'X';
                        }
                    }
                }
            }
        }
    }


    /**
     * dfs返回是否碰到边界
     */
    private void dfs(char[][] board, boolean[][] visit, int x, int y, List<int[]> savedList, List<Boolean> flagMap) {
        savedList.add(new int[]{x, y});
        if (x == 0 || x == board.length-1 || y == 0 || y == board[x].length-1) {
            flagMap.add(0, false);
        } else {
            boolean flag = false;
            int[][] directions = new int[][]{
                    {-1, 0}, {1, 0}, {0, -1}, {0, 1}
            };
            for (int[] direct : directions) {
                int newX = x + direct[0];
                int newY = y + direct[1];
                if (0 <= newX && newX < board.length && 0 <= newY && newY < board[newX].length && !visit[newX][newY] && board[newX][newY] == 'O') {
                    visit[newX][newY] = true;
                    dfs(board, visit, newX, newY, savedList, flagMap);
                }
            }
        }
    }

    public static void main(String[] args) {
        char[][] board = new char[][]{
                {'X','X','X','X'},
                {'X','O','O','X'},
                {'X','X','O','X'},
                {'X','O','X','X'}
        };
        new P130().solve(board);
        showBoard(board);
    }

    public static void showBoard(char[][] board) {
        for (char[] row : board) {
            for (char c : row) {
                System.out.print(c + ",");
            }
            System.out.println();
        }
    }
}
